/*
author:
start_date:
version:
*/

//website:

/*
thought:
*/

#include <iostream>
//#include<list>

#include<ctime>
#include<cmath>


using namespace std;

int  main(void) {

  clock_t start_time=clock();


  int n,sqrtN;
  cin >> n;
  sqrtN = sqrt(n);


  //筛法求素数
  bool * num = new bool[sqrtN];
  for (int j = 0; j < sqrtN; j++) {
    num[j] = true;
  }
  int i = 2;
  //素数判断
  while (i <= sqrtN ) {

      //质因数验证
      int count = 0;
      while (n % i ==0) {
        n = n/i;
        count++;
      }
      if(count >0 )
      {
        cout << i << " " << count << endl;
      }


      for(int j = i*2; j <= sqrtN; j = j+i)
      {
        num[j-1] = false;
      }
      do {
         i++;
      } while(num[i-1] == false);
  }

  if(n != 1)
  {
    cout << n << " " << 1 << endl;
  }


  clock_t end_time=clock();
  cout<< "Running time is: "<<static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1000<<"ms"<<endl;//输出运行时间
  return 0;
}
